#include <iostream>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<assert.h>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
const int maxn = 101010;
int next[maxn],extend[maxn];
char str[maxn],mode[maxn];
void getextendnext(char *mode, int *next,int strlen)
{//求模式串的next数组， 
    int a, p, j = -1;
    next[0] = 0;
    for (int i = 1; i < strlen; i++,j--)
    {
        if (j < 0 || i + next[i - a] >= p)
        {
            if (j < 0) j = 0, p = i;
            while (p < strlen && mode[p] == mode[j])
                ++p, ++j;
            next[i] = j, a = i;
        }
        else next[i] = next[i - a];
    }
}

void getextend(char *str,int strlen, int *extend, char *mode, int modeLen)
{
    getextendnext(mode, next, modeLen);
    int a, p, j = -1; 
    for (int i = 0; i < strlen; i++,--j)
    {
        if (j < 0 || i + next[i - a] >= p)
        {
            if (j < 0) j = 0, p = i;
            while (p < strlen && j < modeLen && str[p] == mode[j])
                ++p, ++j;
            extend[i] = j, a = i;
        }
        else extend[i] = next[i - a];
    }
}

int main()
{	
	int i,j,k;
   strcpy(str,"abababccc");
   strcpy(mode,"aaaaa");
    getextend(str, strlen(str), extend, mode, strlen(mode));
    //  str原串,原串长度，拓展kmp的extend数组，模式串,长度
	for(i=0; i<strlen(str); i++)
		printf("%c ",str[i]);puts("");
	
	for(i=0; i<strlen(mode); i++)
		printf("%c ",mode[i]);puts("");
	for(i=0; i<strlen(mode); i++)
		printf("%d ",next[i]);puts("");
	for(i=0; i<strlen(str); i++)
		printf("%d ",extend[i]);puts("");
    return 0;
}
